Graph / $k$-degenerate graph (Bibtex)

P30: Enumerate well-ordered (strongly) $k$-generate with $n$ vertices

Input:

$n$: the number of vertices.

Output:

All well-ordered (strongly) $k$-degenerate graphs with $n$ vertices.

Complexity:

$O(nm+m^2)$ time per enumerated and printed graph.

Comment:

$m$ is the number of edges of printed graphs.

Reference:

[Bauer2010a] (Bibtex)

P31: Enumerate well-ordered (strongly) $k$-generate with $n$ vertices and $m$ edges

Input:

$n$: the number of vertices, $m$: the number of edges.

Output:

All well-ordered (strongly) $k$-degenerate graphs with $n$ vertices and $m$ edges.

Complexity:

$O(n^{3/2}m^2)$ time per enumerated and printed graph.

Comment:

Reference:

[Bauer2010a] (Bibtex)

P439: Enumeration of all maximal $k$-degenerate induced graph in a chordal graph

Input:

A chordal graph $G = (V, E)$ and an integer $k$.

Output:

All maximal $k$-degenerate induced graphs in $G$.

Complexity:

$O(m\cdot \omega(G)$ time per solution with polynomial space, where $\omega(G)$ is the size of a maximum clique.

Comment:

The number of maximum cliques in a chordal graph is linear in the size of the graph.

Reference:

[Conte2017] (Bibtex)

P506: Enumerate all maximal induced $k$-degenerate subgraphs in a graph

Input:

A graph $G=(V, E)$ and an integer $k$.

Output:

All maximal induced $k$-degenerate subgraphs in $G$.

Complexity:

$O(mn^{k+2})$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)

P507: Enumerate all maximal connected induced $k$-degenerate subgraphs in a graph

Input:

A graph $G=(V, E)$ and an integer $k$.

Output:

All maximal connected induced $k$-degenerate subgraphs in $G$.

Complexity:

$O(mn^{k+3})$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)

P508: All maximal $k$-degenerate edge subgraphs in a graph

Input:

A graph $G=(V, E)$ and an integer $k$.

Output:

All maximal $k$-degenerate edge subgraphs in $G$.

Complexity:

$O(\binom{n}{k-1}m^3)$ delay.

Comment:

Exponential space. Proximity search.

Reference:

[Conte2019] (Bibtex)